package com.jin.one;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * 归并排序
 * @author Jin
 * @time 2012-12-4下午9:02:33
 */
public class MergeSort {
	static int count=0;
	public static void main(String[] args) {
		while(true){
			System.out.println("\n请输入一组整数，以空格隔开，非数字字符结束，按Enter查看结果：");
			Scanner scan=new Scanner(System.in);
			ArrayList<Integer> list=new ArrayList<Integer>();
			while(scan.hasNextInt()){
				list.add(scan.nextInt());
			}
			int[] arr=new int[list.size()];
			for(int j=0;j<arr.length;j++){
				arr[j]=(Integer)list.get(j);
			}
			sort(arr);
			for(int i=0;i<arr.length;i++){
				System.out.print(arr[i]+"\t");
			}
			System.out.println("完成此次排序的比较次数是："+count);
		}
	}
	
	public static void sort(int[] data) {
		int[] temp = new int[data.length];
		mergeSort(data, temp, 0, data.length - 1);
	}

	private static void mergeSort(int[] data, int[] temp, int l, int r) {
		int mid = (l + r) / 2;
		if (l == r)
			return;
		mergeSort(data, temp, l, mid);
		mergeSort(data, temp, mid + 1, r);
		for (int i = l; i <= r; i++) {
			temp[i] = data[i];
		}
		int i1 = l;
		int i2 = mid + 1;
		for (int cur = l; cur <= r; cur++) {
			if (i1 == mid + 1)
				data[cur] = temp[i2++];
			else if (i2 > r)
				data[cur] = temp[i1++];
			else if (temp[i1] < temp[i2])
				data[cur] = temp[i1++];
			else
				data[cur] = temp[i2++];
			count++;
		}
	}
}
